package com.jike.jkgame.data;


public class Tree<T> {
	
	private TreeNode<T> root_;
	
	public Tree() {}
	
	public TreeNode<T> getRoot() {
		return root_;
	}
	
	public void setRoot(TreeNode<T> root) {
		root_ = root;
	}
	
	public int getNumberOfNodes() {
		int numberOfNodes = 0;
		if(root_ != null) {
			numberOfNodes += recursiveGetNumberOfNodes(root_) + 1;
		}
		return numberOfNodes;
	}
	
	public boolean exists(T data) {
		return find(data) != null;
	}
	
	public TreeNode<T> find(T data) {
		TreeNode<T> returnNode = null;
		if(root_ != null) {
			returnNode = recursiveFind(root_, data);
		}
		return returnNode;
	}
	
	public boolean isEmpty() {
		return root_ != null;
	}
	
	private int recursiveGetNumberOfNodes(TreeNode<T> node) {
		int numberOfNodes = node.getNumberOfChildren();
		for(TreeNode<T> child : node.getChildren()) {
			numberOfNodes += recursiveGetNumberOfNodes(child);
		}
		return numberOfNodes;
	}
	
	private TreeNode<T> recursiveFind(TreeNode<T> node, T data) {
		TreeNode<T> target = null;
		if(node.getData().equals(data)) {
			target = node;
		} else if(node.hasChildren()) {
			for(TreeNode<T> child : node.getChildren()) {
				target = recursiveFind(child, data);
				if(target != null) {
					break;
				}
			}
		}
		return target;
	}
	
	//test code
	/*
	   A
	  / \
	 B   C
	    / \
	   D   E
	        \
	         F
	 */
	public static void main(String[] args) {
		Tree<String> tree = new Tree<String>();
		TreeNode<String> A = new TreeNode<String>("A");
		TreeNode<String> B = new TreeNode<String>("B");
		TreeNode<String> C = new TreeNode<String>("C");
		TreeNode<String> D = new TreeNode<String>("D");
		TreeNode<String> E = new TreeNode<String>("E");
		TreeNode<String> F = new TreeNode<String>("F");
		
		tree.setRoot(A);
		A.addChild(B);
		A.addChild(C);
		C.addChild(D);
		C.addChild(E);
		E.addChild(F);
		
		System.out.println(tree.find("E").getData());
		System.out.println(tree.find("B").getData());
	}
}
